package arithmetic1.greed;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Test {

    public static void main(String[] args) {
        // 创建广播台
        HashMap<String, HashSet<String>> broadcast = new HashMap<String, HashSet<String>>();
        HashSet<String> hashset1 = new HashSet<String>();
        hashset1.add("北京");
        hashset1.add("上海");
        hashset1.add("天津");

        HashSet<String> hashset2 = new HashSet<String>();
        hashset2.add("广州");
        hashset2.add("上海");
        hashset2.add("深圳");

        HashSet<String> hashset3 = new HashSet<String>();
        hashset3.add("成都");
        hashset3.add("上海");
        hashset3.add("杭州");

        HashSet<String> hashset4 = new HashSet<String>();
        hashset4.add("上海");
        hashset4.add("天津");

        HashSet<String> hashset5 = new HashSet<String>();
        hashset5.add("杭州");
        hashset5.add("大连");

        broadcast.put("A", hashset1);
        broadcast.put("B", hashset2);
        broadcast.put("C", hashset3);
        broadcast.put("D", hashset4);
        broadcast.put("E", hashset5);

        // 创建一个所有地区的
        HashSet<String> allAreas = new HashSet<String>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");

        // 使用一个电台集合
        ArrayList<String> selects = new ArrayList<String>();

        // 临时变量,覆盖的地区和未覆盖地区的交集
        HashSet<String> temp = new HashSet<String>();

        // 定义一个在一次遍历过程中覆盖最多地区的广播台
        String maxKey = null;
        while (allAreas.size() != 0) {
            // 遍历广播台
            for (String key : broadcast.keySet()) {
                temp.clear();
                HashSet<String> areas = broadcast.get(key);
                temp.addAll(areas);
                // 取交集,之后交集再赋给temp
                temp.retainAll(allAreas);
                if (temp.size() > 0 && (maxKey == null || temp.size() > broadcast.get(maxKey).size())) {
                    maxKey = key;
                }
            }
            if (maxKey != null) {
                selects.add(maxKey);
                allAreas.removeAll(broadcast.get(maxKey));
            }
            maxKey = null;
        }
        System.out.println("结果：" + selects);
    }

}
